Electronic design automation ("EDA") is becoming increasingly complicated and time consuming, due in part to the greatly increasing size and complexity of the electronic devices designed by EDA tools. Such devices include general purpose microprocessors as well as custom logic devices including Application Specific Integrated Circuits ("ASICs"). Examples of ASICs include non-programmable gate arrays, field programmable gate arrays ("FPGAs"), and complex programmable logic devices ("PLDs" or "CPLDs"). The design of even the simplest of these devices typically involves generation of a high level design, logic simulation, generation of a network, timing simulation, etc. Usually, timing simulation cannot be performed until the design has been compiled to the point where the various gate level entities are synthesized and placed and the lines therebetween routed on a target hardware device. This compilation requires that a design project (or a significant piece of it) be functionally completed.
Meeting timing requirements is essential to the correct operation of an integrated circuit. For example, for a plurality of D-type flip-flops ("DFFs") to feed through some logic to another plurality of DFFs, it is generally required that the signals form the first set of DFFs must finish propagating through any intermediate logic and have settled to their final state on the D-input of each of the destination DFFs before the next rising edge of the clock. (In fact they must finish before the next clock edge by an amount known as the setup delay of the register T.sub.su.) If the delay through the resulting logic is greater than the time between rising clock edges, then the state that the destination DFFs will hold on the next clock edge will be undefined.
Quite typically, a designer (or the compiler itself) will modify a design after an initial compilation. This may be required when a timing simulation conducted after compilation indicates a problem. Or, the product requirements may change in the middle of the device's development. Regardless of why a design change is necessary, that change requires a recompile. Unfortunately, each compilation consumes significant time, so multiple recompiles translates to significantly longer development times. This can greatly slow the time to market for an integrated circuit under design. Because PLDs rely on a short time to market as a major selling point, slow development can erase any commercial advantage.
The problem is compounded because maximum CPLD device sizes are increasing at a speed slightly greater than that predicted by Moore's law, (i.e., each new chip contains roughly twice as much capacity as its predecessor, and each chip is released within 18-24 months of the previous chip). If compilation time was a linear function of design size then it would be expected that the time to compile the largest device on the most powerful computer would remain approximately constant. Unfortunately, compile times are typically proportional to n.sup.2, where n is the number of logic elements on a device. This means that a design twice as big takes four times as long to compile. Consequently, the compile times for the largest devices are accelerating. It is not uncommon for large projects to compile for about 24 hours or more on a modern workstation. Obviously, the fastest compilers will become critical components of integrated circuit design environments.
Large designs often benefit from performing and comparing multiple compilations, each based upon a different compilation parameters or slight design changes. For example, the heuristics for synthesizing and/or the heuristics for mapping a design can be varied to emphasize different goals (e.g., speed versus compact fit). Obviously, given long compile times, most designers do not have the luxury of running multiple compilations for comparison.
An important advance in the effort to reduce compilation time for large complex devices is incremental compilation. In essence, incremental compilation involves using a previously compiled design such that only a fraction of that design must be recompiled after a user makes one or more changes to the design. Incremental compilation requires at least two steps: (1) delineating a sphere of influence of user changes in a previously compiled design (the sphere of influence typically being defined within a netlist), and (2) recompiling the logic from within this sphere of influence into appropriate logic elements available within a target hardware device. To maximize efficiency, the compiler should minimize changes to portions of the electronic design (and corresponding regions of a target hardware device) which are not directly affected by the design change.
One suitable technique for delineating a sphere of influence of user changes to a previously compiled design (step 1) is a "netlist differencing" procedure followed by a "sub-netlist" identification algorithm. Netlist differencing is described in U.S. patent application Ser. No. 08/619,073, filed on Mar. 20, 1996, naming Lee as inventor and entitled "METHODS FOR IMPLEMENTING CIRCUIT DESIGNS IN PHYSICAL CIRCUITS." A sub-netlist identification algorithm is described in U.S. patent application Ser. No. 08/952,002, filed on the same day as the instant patent application, naming B. Pedersen et al. as inventors and entitled "GENERATION OF SUB-NET LISTS FOR USE IN INCREMENTAL COMPILATION." Both of these documents are incorporated herein by reference for all purposes.
At this point, an effective incremental compiler cannot be realized until a technique for placing changed portions of an electronic design is developed. Thus, there is a need for a technique that efficiently and correctly places changed logic cells during incremental recompile.